package interview7;

/**
 * @author Jack
 * @date 2019-11-03-15:26
 * 面试题7：重建二叉树
 */
public class Solution {

    public static void main(String[] args) {
        int[] preOrder = new int[]{1, 2, 4, 5, 3, 6, 7};
        int[] inOrder = new int[]{4, 2, 5, 1, 6, 3, 7};
        Node root = construct(preOrder, inOrder, 0);
        System.out.print("中序遍历二叉树:");
        inOrderOutputTree(root);
        System.out.println();
        System.out.print("前序遍历二叉树:");
        preOrderOutputTree(root);
        System.out.println();
        System.out.print("后序遍历二叉树:");
        reOrderOutputTree(root);
    }

    private static void reOrderOutputTree(Node root) {
        if(root == null){
            return ;
        }
        if(root.leftChild != null){
            reOrderOutputTree(root.leftChild);
        }
        if(root.rightChild != null){
            reOrderOutputTree(root.rightChild);
        }
        System.out.print(root.value+" ");
    }

    private static void preOrderOutputTree(Node root) {
        if(root == null){
            return ;
        }
        System.out.print(root.value+" ");
        if (root.leftChild != null){
            preOrderOutputTree(root.leftChild);
        }
        if (root.rightChild != null){
            preOrderOutputTree(root.rightChild);
        }
    }

    public static void inOrderOutputTree(Node node){
        if(node == null){
            return ;
        }
        if(node.leftChild != null){
            inOrderOutputTree(node.leftChild);
        }
        System.out.print(node.value+ " ");
        if(node.rightChild != null){
            inOrderOutputTree(node.rightChild);
        }
    }


    public static Node construct(int[] preOrder, int[] inOrder, int rootIndex) {
        if (preOrder == null || inOrder == null || preOrder.length == 0 || inOrder.length == 0) {
            return null;
        }
        boolean isValid = false;
        Node node = new Node();
        node.value = preOrder[rootIndex];
        node.leftChild = null;
        node.rightChild = null;
        for (int i = 0; i < inOrder.length; i++) {
            if (preOrder[rootIndex] == inOrder[i]) {
                isValid = true;
                int[] leftInOrderTree = new int[i];
                int[] leftPreOrderTree = new int[i];
                for (int j = i; j > 0 ; j--) {
                    leftInOrderTree[i - j] = inOrder[i - j];
                }
                for (int j = 0; j < i; j++) {
                    leftPreOrderTree[j] = preOrder[rootIndex+j+1];
                }
                Node leftChild = construct(leftPreOrderTree, leftInOrderTree, rootIndex);
                node.leftChild = leftChild;
                int[] rightInOrderTree = new int[inOrder.length - i - 1];
                int[] rightPreOrderTree = new int[inOrder.length - i - 1];
                for (int j = 0; j < rightInOrderTree.length; j++) {
                    rightInOrderTree[j] = inOrder[i+j+1];
                }
                for (int j = 0; j < rightPreOrderTree.length; j++) {
                    rightPreOrderTree[j] = preOrder[j + leftPreOrderTree.length + 1];
                }
                Node rightChild = construct(rightPreOrderTree, rightInOrderTree, rootIndex);
                node.rightChild = rightChild;
            }
        }
        if(!isValid){
            throw new RuntimeException("输入不合法！");
        }
        return node;
    }

}

class Node{

    public int value;
    public Node leftChild;
    public Node rightChild;

}